When information is transmitted over a communications link between a receiver and a transmitter, the bits that describe the information being transmitted can be corrupted. In other words, the receiver may determine that a received bit that is supposed to be a binary 1 is a binary 0, and vice versa. Corruption of bits in a data stream may be caused by a variety of factors or components in the communications link. For example, in an optical fiber network, optical energy is transmitted in the form of optical pulses that have particular levels that correspond to binary 1s and 0s. If the level of the optical energy is too low, the receiver can have difficulty determining whether a pulse corresponds to a binary 1 or a binary 0. Repeaters, or amplifiers, normally are disposed at particular locations along the communications link that amplify the optical signals so that they are at the proper levels to enable the receiver to determine whether it has received a binary 1 or a binary 0. Typically, the optical signals are converted into electrical signals at the repeaters. The electrical signals are then amplified and converted into optical signals, which are then modulated back onto the optical fiber. Similarly, at the receiver, the optical signals typically are converted back into electrical signals, which the receiver compares to a threshold value to determine whether it has received a binary 1 or a binary 0.
Because it is possible for the bits to be corrupted, techniques have been developed and implemented that provide error correction. In other words, if a bit received by the receiver is erroneously determined to be a binary 1 when it was meant to be a binary 0 when it was transmitted, and vice versa, receivers utilize various techniques to determine whether a bit value has been incorrectly identified and to correct the bit value. One known technique used for such purposes is generally referred to as the “Automatic Repeat Request” (ARQ) technique. In accordance with this technique, when the receiver detects a bit error, it sends a signal to the transmitter that tells the transmitter to retransmit the block of data that contained the error. The receiver processes the retransmitted data block and detects bit errors. The data block may need to be retransmitted several times before the receiver determines that the data is without error. Of course, retransmitting data utilizes bandwidth and generally slows down the overall throughput of the communications system.
A technique known as Forward Error Correction (FEC) is commonly used in the communications industry to reduce errors in data being transmitted over a communications link without requiring retransmission of data. FEC not only detects bit errors, but corrects detected bit errors. One of the primary advantages of FEC over ARQ is that no retransmission of data is required with FEC. This is because FEC techniques introduce redundancy in the data bits that enables the receiver of a communications system to detect errors in data being transmitted and to correct the detected errors. The redundancy generally is introduced by utilizing data bits from the data stream to encode the data stream. The receiver has a decoder that has intelligence with regard to the encoding scheme used by the transmitter, which enables the receiver to decode the data and detect and correct errors without the need for retransmission. Another advantage of FEC is that, because it does not require retransmission of data, simplex links can be used, which is desirable in certain situations, such as when the receivers are receive-only terminals.
Generally, FEC techniques and systems fall into two broad categories, namely, block coding and convolution coding. Various block coding and convolution coding techniques are currently in use in the communications industry. In the past, the use of block codes has generally been limited to use in communications systems that have relatively low data rates for various reasons, such as the aforementioned adverse effects on overall coding gain (signal-to-noise ratio, Eb/No), which is expressed in decibels (dB), for short data bursts and the reduced overall throughput that can result from the synchronization requirement. Convolution coding has generally been the preferred FEC technique for high data rate implementations. However, convolution coding results in higher output bit error rates (BER) than the output (BERs) that can be achieved using block coding. Some customers want FEC systems with very low BERs (e.g., 10−15), which generally cannot be achieved using convolution coding, but which can be achieved using block coding, such as Bose-Chaudhuri-Hocquenghem (BCH) block coding, for example.
FEC decoding requires that a vector known as the syndrome vector be computed by multiplying the code word received by the decoder of the FEC system receiver by a matrix known as the parity-check matrix. This syndrome vector is then processed in accordance with a Berlekamp algorithm, which generates an error location polynomial. The error correction polynomial, once resolved, is analyzed in accordance with a Chien search algorithm, which determines the actual locations of the bit errors in the received code word. The Chien search engine then passes results to an error correction logic block which exclusive-ORs (XORs) the output from the Chien search engine with delayed corresponding bits of the code word, which causes the bits that are erroneous to be inverted and thereby corrected.
Generally, the Chien search algorithm finds the 0s in the error locator polynomial X by evaluating the polynomial at all possible values of X and flagging all values that result in a zero output. The Chien search algorithms commonly employed in decoders utilize a large matrix having values that are multiplied by the coefficients of the error locator polynomial. After the matrix multiplication operations have been performed, the Chien search algorithm checks the results of the operations for 0s. Because the matrix that is multiplied by the error locator polynomial coefficients is very large, a large number of logical operations would need to be performed, which would require a large number of logic gates. The large number of logic gates would consume a large area on the decoder integrated circuit (IC) and would also consume a large amount of power.
In order to avoid using such a large number of logic gates, the typical Chien algorithm uses a shift register approach, which requires a very small amount of logic, but which can only process one bit per cycle. This approach generally is suitable for low data rate systems, but in order for such an approach to be used in a high data rate system, the system would have to operate at a prohibitively fast clock speed. Consequently, the commonly used Chien search algorithms are not suitable for use in high data rate communications systems.
A need exists for a method and apparatus for performing the Chien search algorithm quickly with a relatively small amount of logic so that a large amount of area from being required for implementation of the algorithm logic, power consumption is kept relatively low and the decoder can be used in high data rate systems.